1. Field of the Invention
The invention relates to a image processing device and image processing method, and more particularly, to a image processing device and image processing method for functionally approximating an outline and center line of figures.
2. Description of the Related Art
Nowadays, digitalization of existing data for reuse has become common due to increasing demands on paperless data. Traditionally, image data were reused in such a way that the data is converted into vector data using vectorization techniques after binarization, then utilized with CAD software, etc.
Meanwhile, recently, environmental problems are emphasized even in office. As a solution for the problem, efforts to move from a paper-based system are mounting rapidly. As one way of achieving the efforts, paper documents can be read with a scanner, converted into the corresponding electronic data, and then stored. However, there is another problem that while the paper documents can be maintained as electronic data, the documents themselves cannot be reused since the files themselves are in image format. Furthermore, even when the documents are stored in storage media, there would be tradeoff problems between image qualities of the stored image information and the capacity of a storage area for storing the electronic data. For instance, the file size of an electronic data would be large if the data is stored in high quality.
One way of simultaneously solving above two problems resulting in a tradeoff is to divide read images into objects such as character area, photo image area, line-drawing area, table area, etc. and vectorize them respectively such that capacity for digitized image data can be reduced. In this case, data amount can be reduced and thus high-quality and reusable electronic documents can be obtained, by binarizing areas such as character, line-drawing, and table, etc. as binary image area and vectorizing them with outlining process (hereinafter, also referred to as “outline vectorization”).
As for binary image data vectorization, the applicant already proposed the Japanese Patent Publication No. 3026592. In this document, the following configuration is disclosed.
That is, a process is performed in which predefined positions are selected as those which make up a profile line based on the statuses of a pixel of interest and its neighboring pixels and then the connection direction of points is determined based on points and other points also making up the profile line. Then, a process is performed which determines the statuses of the connection between the points and other points also making up the profile line. Then, the location of the pixel of interest will be updated in raster scan order on the image data, and the above process is repeatedly performed with respect to each pixel of interest based on the statuses of the neighboring pixels, and finally, contour points are extracted. As for the above configuration, both the statuses of the pixel of interest and the neighboring pixels in the image data are retained, and the pixel of interest is extracted in raster scan order, and a horizontal and vertical inter-pixel vectors is detected based on the statuses of the pixel of interest and the neighboring pixels. The status of the connection between those inter-pixel vectors is determined, and the outline of the image data is extracted based on the statuses. The Japanese Patent Publication No. 3026592 proposed the method described above.
Since the method described in the Japanese Patent Publication No. 3026592 can extract all of the profile lines within an image in only one raster scan, and even does not need any image memory for storing all image data, it has an advantage of reduced memory capacity. Additionally, since the method extracts profile lines by pixel edge of an input image rather than by the center point thereof, it has promising width for a thin line of one pixel width. Furthermore, the document discloses that it can extract not only profile lines connected in four directions but also those connected in 8 directions in an original image.
In addition, the applicant disclosed in the Japanese Patent Laid-Open No. H05-108823(1993) that an efficient profile line extraction could be achieved by modularizing the vector extraction rule disclosed in the Japanese Patent Publication No. 3026592.
Meanwhile, the applicant also proposed the Japanese Patent Publication No. 3049672. In this document, an image processing device is disclosed which can obtain high-quality variable images using binary image profile information. In this proposition, outline vectors are extracted from a binary image, and the outline vectors are created by smoothly scaling the extracted outline vector at desired (arbitrary) magnification, and a binary image is regenerated from the scaled vectors. As a result, a high-quality digital binary image scaled at desired (arbitrary) magnification can be obtained. Note that as a way of extracting online vectors from a binary image, the above method disclosed in the Japanese Patent Publication No. 3026592 and the Japanese Patent Laid-Open No. H05-108823(1993) may be used, for example.
Additionally, the applicant also proposed the Japanese Patent Laid-Open No. 2005-346137. In this document, a processing method and device are disclosed which functionally approximate profile information with small data amount which represents high-quality variable images by performing not only straight-line approximation but also second- or third-order Bezier curve approximation. The high-quality variable image scaled at desired (arbitrary) magnification can also be obtained by using the online vectors which are created by extracting online vectors from a binary image and smoothly and functionally approximating the extracted vectors in the same way as described in the Japanese Patent Laid-Open No. 2005-346137. Here, as a way of extracting outline vectors from a binary image, the methods disclosed in the Japanese Patent Publication No. 3026592 or the Japanese Patent Laid-Open No. H05-108823(1993) described above may be used.
FIG. 2A to 2D illustrates exemplary process of an outline vectorization sequence for the above binary image. Specifically, the figures show data appearance in a sequence for obtaining high-quality digital binary image scaled at desired (arbitrary) magnification by using the online vectors which are created by extracting online vectors from a binary image and smoothly and functionally approximating the extracted vectors.
FIG. 2A illustrates an example of an input binary image. FIG. 2B illustrates an outline vector depicted and visualized as an outline image which can be extracted from the binary image in FIG. 2A with the method disclosed in the Japanese Patent Publication No. 3026592 or the Japanese Patent Laid-Open No. H05-108823(1993). FIG. 2C depicts and visualizes an outline vector obtained by smoothly and functionally approximating the extracted outline vector data with the method disclosed in the Japanese Patent Laid-Open No. 2005-346137. FIG. 2D illustrates an example of a high-quality digital binary image scaled at desired (arbitrary) magnification which can be obtained by middle-coating the leveled (functionally approximated) vector.
As previously described, due to growing demands on paperless, digitalization and reuse of existing image data are desired even for business documents. A type of reuse in which an original image is scaled at desired magnification, inter alia, can be achieved by the Japanese Patent Publication No. 3026592 or the Japanese Patent Laid-Open No. H05-108823(1993) and the Japanese Patent Laid-Open No. 2005-346137. That is, it can be achieved by extracting the profile (outline) vectors from a binary figure in an original document and scaling its two-dimensional shape at arbitrary scaling rate.
An outline-vectorized electronic documents can be obtained by extracting profile lines obtained from a binary image and functionally approximating curves of the obtained profile lines with curve functions such as the Bezier curve, etc. as described above. Note here that when functionally approximating with such curve functions, typically, it is necessary to calculate a point sequence on a profile line and errors of the Bezier curve and to optimize the curve, resulting in possible significant repetitive operations and very long processing time.
As approximate calculation which might shorten the processing time, a method of interpolating profile points with a curve is contemplated. However, it might cause a problem that if curve interpolation is applied directly to the profile points, then the number of interpolation points might increase and thus compression effect of outline vectorization might be depleted. Additionally, if the number of interpolation points is cut down with straight-line approximation etc., another processing time would be needed for the approximation. That is, although data amount may be reduced with outline vectorization, large amount of operations and significant operation time would be needed for approximation calculation in the vectorization. Consequently, a problem would occur that enough reduction effect in data amount cannot be obtained even when trying to shorten the operation time with performing outline vectorization.
So the leveling (functional approximation) process of profile vectors in the Japanese Patent Laid-Open No. 2005-346137 described above basically determines anchor points which specify an interval to be functionally approximated with curve functions such as Bezier curve, etc. as described bellow. That is, the anchor points are determined based on the combinations of the direction or length of series of edge vector around the edge vector of interest. The Japanese Patent Laid-Open No. 2005-346137 arranges a profile point sequence in an interval divided by the anchor points such that the sequence approximated with the Bezier curve. In this way, significant repetitive operations traditionally performed for obtaining a point sequence on a profile line and optimizing the curve would not be necessary, and an outline vectorization is made possible which does not cost significant processing time such as in the prior art
According to the Japanese Patent Laid-Open No. 2005-346137, vector leveling (functional approximation) is performed as follows. First, profile data, called rough profile data, composed of horizontal and vertical vectors aligning one after the other which are extracted from binary raster image data are entered, then tangential lines are computed from lines on the rough profile. Anchor points are extracted from the extracted tangential lines. Then, a straight-line is applied to the group of one or multiple lines between the extracted anchor points, or a second- or third-order Bezier curve is applied to them in order to perform Bezier curve approximation, and the above lines are replaced with the straight-line or second- or third-order Bezier curve.
Here, note that the method of functionally approximating profile points between anchor points as one group based on the points defined as anchor points is the basic means for functional approximation techniques. Also, anchor points have a characteristic that the positions (coordinate values) of the anchor points themselves do not change even if the interval defined by the points is functionally approximated with any of a second- or third-order Bezier curve or a straight-line.
According to the Japanese Patent Laid-Open No. 2005-346137, there are several conditions for extracting candidate vectors for tangential line segment:    the preceding vector and the next vector of the candidate vectors should be in opposite direction with respect to one another;    the candidate vectors should be adjacent to the extracted main tangential line segment, and the length of the vectors L1 should satisfy L1≧θ4;    the length of the vectors L2 should satisfy L2≧θ5 
where θ4 and θ5 are predefined constants, respectively.
As for extraction of anchor points, new points are extracted on the extracted tangential line segments as anchor points. The anchor points are extracted for the both edges of the tangential line segment. Therefore, basically, two anchor points are extracted for one tangential line segment. However, if the two anchor points are the same, then one anchor point will be extracted. If two anchor points are extracted, the segment sandwiched between the anchor points are automatically interpolated with a straight-line on the object. As a way of extracting anchor points for the one edge of a tangential line segment, if a vector adjacent to the tangential line segment vector of interest is a tangential line segment, the end points of the adjacent vector will be anchor points. Otherwise, a point will be selected as an anchor point which is on the vector adjacent to the adjacent line segment, i.e., the vector V1 (its length is represented as |V1|) of the line segment that is two segments before the vector V2 (its length is represented as |V2|) of the tangential line segment of interest and which is distant by a |V2| from the end points on the V2 vector.
Additionally, it is disclosed in the Japanese Patent Laid-Open No. 2005-346137 that functional approximation of the profile point sequence in the interval determined as described above can be performed as follows. First, as shown in FIG. 8 (corresponding to FIG. 19 of the Japanese Patent Laid-Open No. 2005-346137), take N points p1, p2, . . . , pN which make up the profile line sequence in an interval to be functionally approximated by curve functions such as the Bezier curve, etc. where p1 and pN are the anchor points of the interval. Then, a point pf on the curve is determined which is farthest distant from the line segment p1pN connecting the anchor points p1 and pN. In order to easily perform functional approximation, the approximation is done such that the line segment C1C2 connecting control point is parallel to the line segment p1pN. Then, the control points C1 and C2 are determined such that the distance from the points C1 and C2 to the line segment p1pN is (4/3)×L, where L is the distance from the point pf to the line segment p1pN.
That is, when the coordinate value of pf is (pfx, pfy), using the coordinate values (p1x, p1y) of p1 and the coordinate values (pNx, pNy) of pN and the tangential vector p1C1 (pcx, pcy), the coordinate value (C1x, C1y) of C1 will be:C1x=K×pfx+p1x C1y=K×pfy+p1y K=(3p1x−4pfx)(pNy−p1y)+(pNx−p1x)(4pfy−3p1y)+p1x(pNy−p1y)−p1y(pNx−p1x)/(3(pNy−p1y)pcx+3(pNx−p1x)pcy)and can be uniquely determined by the coordinate of pf. Also, C2 can be determined in the same way as for C1. Note that the above dividing points are anchor points. Also, a tangential vector at the anchor points is determined by extracting a directional vector in a pattern matching manner from a combination of multiple line segments upon dividing into segment curves.
The above process is disclosed in the Japanese Patent Laid-Open No. 2005-346137.
In this way, the Japanese Patent Laid-Open No. 2005-346137 discloses a process which does not need any significant repetitive operations typically performed in the prior art for determining a point sequence on a profile line and errors of the Bezier curve and optimizing the curve. That is, outline vectorization is disclosed in the document which does not need any significant process time as in the prior art.
By the way, digital copy machines are being replaced by digital multi function peripheral equipments which have multiple functions such as image transmission, image storage, image copying, image printing, etc. These equipments are systematically composed of scanner units for reading document images, digital printer units, digital image data processing units, data sending and receiving units, data storage management units, etc. Having the electronic documents generation features described above, these equipments will contribute significantly to improvement in an office environment.
When these equipments have the electronic documents generation feature described above, device cost, processing time, etc. thereof must be limited for their practical use. Although it will be better if high-speed and high approximation accuracy vectorization is performed in relatively small data amount, there is certain tradeoff between speed, approximation accuracy, and data amount. That is, there is a tendency that if data amount is increased by increasing anchor points, then each interval for functional approximation can be narrowly created and generally more accurate functional approximation can be performed. Also, by increasing processing time, parts of comparatively less accurate vectorization may also be improved.
The profile vector leveling (functional approximation) disclosed in the Japanese Patent Laid-Open No. 2005-346137 is considered to be superior and a very useful technique in that it enables outline vectorization which does not needs any significant processing time such as in the prior art. That is, with the profile line leveling (functional approximation) described above, significant repetitive operations for obtaining a point sequence on a profile line and errors of the Bezier curve and optimizing the curve would not be necessary, and an outline vectorization which does not require significant processing time such as in the prior arts will be made possible. However, the technique disclosed in the document did not include a mechanism for optimizing data amount, processing time, and approximation accuracy in view of such tradeoffs.
The present invention, conceived to address the above problems, has an objective to provide a image processing device and image processing method to improve within the limitation of data amount the accuracy of Bezier approximation with relatively high-speed processing, and to improve the accuracy in pre-defined processing time. In other words, the purpose of the invention is to propose a specific processing configuration which enables vectorization based on functional approximation with improved accuracy relative to the traditional ones with some limitations of practical device configuration or processing time.